package 集合.stack;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/** 
 *@author TonyJ 
 *@time 2011-6-17 下午03:44:49 
 */  
public class InfixMain {  
    public static void main(String[] args) {  
        String input, output;  
//        while (true) {  
//           input = getString();
//      	  
//            if ("".equals(input) || input == null) {  
//                break;  
//            }
//            
//            InToPost itp = new InToPost(input);  
//            output = itp.doTrans();  
//            System.out.println("Profix is " + output + "\n");  
//        }
        input="(10+20/2*30)/2+8";
        input=insertBlanks(input);
        String[] input1 = input.split(" ");
        System.out.println(Arrays.toString(input1));
        InToPost itp = new InToPost(input1);  
        output = itp.doTrans();
        System.out.println("Profix is " + output + "\n");
    }  
  
    public static String getString() {  
        String output = "";  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        try {  
            System.out.println("请输入算术表达式：");  
            output = br.readLine();  
        } catch (IOException e) {  
            e.printStackTrace();  
        }  
        return output;  
    }
    static String insertBlanks(String expression) {
 		StringBuilder sb = new StringBuilder();
 		// 遍历表达式
 		for (int i = 0; i < expression.length(); i++) {
 			char c = expression.charAt(i);
 			// 如果是符号，则在符号前后增加空格
 			if (c == '(' || c == ')' || c == '+' || c == '-' || c == '*' || c == '/') {
 				sb.append(" ");
 				sb.append(c);
 				sb.append(" ");
 			} else { // 如果遇到数字 则原封不动添加在sb
 				sb.append(c);
 			}
 		}
 		return sb.toString();
 	}
    static boolean isOperator(String token) {
 		return "+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token);
 	}
    static boolean isNumber(String token) {
 		return token.matches("\\d+"); // \\d+匹配的是表示多个数字
 	}
}
/** 
 *@author TonyJ 
 *@time 2011-6-17 下午02:24:47 
 */  
class MyStack {  
    private int maxSize;//栈的最大容量  
    //private char[] ch;  //栈的数据  
    private String[] ch;  //栈的数据  
    private int top;    //栈头标记  
  
    public MyStack(int s) {  
        maxSize = s;  
        //ch = new char[s];  
        String[] ch = new String[s];  
        top = -1;  
    }  
  
    //public void push(char c) {//入栈  
    public void push(String c) {//入栈  
        ch[++top] = (String) c;  
    }  
  
    public String pop() {//出栈  
        return ch[top--];  
    }  
  
    public String peek() {  
        return ch[top];  
    }  
  
    public boolean isEmpty() {  
        return top == -1;  
    }  
  
    public boolean isFull() {  
        return top == (maxSize - 1);  
    }  
  
    public int size() {  
        return top + 1;  
    }  
  
    public String get(int index) {  
        return ch[index];  
    }  
  
    public void display(String str) {  
        System.out.print(str);  
        System.out.print(" Stack (bottom-->top): ");  
        for (int i = 0; i < size(); i++) {  
            System.out.print(get(i)+" ");  
        }  
        System.out.println();  
    }  
}

/** 
 *@author TonyJ 
 *@time 2011-6-17 下午02:43:48 
 */  

class InToPost {  
    private MyStack ms;//自定义栈  
    private String[] input;//输入中缀表达式  
    private String output="";//输出的后缀表达式  
  
    public InToPost(String[] input) {  
        this.input = input;  
        //int size = input.length();  
        int size = input.length;  
        ms = new MyStack(size);  
    }  
  
    public String doTrans() {//转换为后缀表达式方法  
        for (int i = 0; i < input.length; i++) {  
            String ch = input[i];  
            //char ch = input.charAt(i);  
            ms.display("for " + ch + " ");       
            switch (ch) {  
            case "+":  
            case "-":  
                getOper(ch, 1);  
                break;  
            case "*":  
            case "/":  
                getOper(ch, 2);  
                break;  
            case "(":  
                ms.push(ch);  
                break;  
            case ")":  
                getParent(ch);  
                break;  
            default://相当于：case 数字:
            	
                output = output + ch;
//                System.out.print(ch);
                break;  
            }//end switch   
        }//end for  
        while(!ms.isEmpty()){  
            ms.display("While ");  
            output=output+ms.pop();  
        }  
        ms.display("end while!!");  
        return output;  
    }  
      
    /** 
     * @param ch 
     * 获得上一级字符串 
     */  
    public void getParent(String ch) {  
        while(!ms.isEmpty()){  
            String chx=ms.pop();  
            if(chx=="("){  
                break;  
            }else{  
                output=output+chx;  
            }  
        }  
    }  
  
    /** 
     * @param ch 操作符 
     * @param prec1 操作符的优先级 
     * 根据操作符的优先级判断是否入栈，及入栈的顺序 
     */  
    //public void getOper(char ch, int prec1) {  
    public void getOper(String ch, int prec1) {  
        while (!ms.isEmpty()) {//判断栈是否为空  
            String operTop = ms.pop();  
            if (operTop == "(") {  
                ms.push(operTop);  
                break;  
            } else {  
                int prec2;  
                if (operTop == "+" || operTop == "-") {  
                    prec2 = 1;  
                } else {  
                    prec2 = 2;  
                }  
                if (prec2 <prec1) {  
                    ms.push(operTop);  
                    break;  
                } else {  
                    output = output + operTop;  
                }  
            }  
        }// end while  
        ms.push(ch);  
    }  
} 
